package com.jia.leetCode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 438. 找到字符串中所有字母异位词
 */
public class Pro0438 {
    /**
     * 双指针，维护固定大小的窗口，统计len长度。如果len长度和p长度一种说明命中。
     * 接下来左边边界收缩，进入下一轮循环
     * @param s
     * @param p
     * @return
     */
    public List<Integer> findAnagrams(String s, String p) {
        char[] sChars = s.toCharArray();
        char[] pChars = p.toCharArray();
        int[] curAtoZ = new int[26];
        int[] aToZ = new int[26];
        List<Integer> result = new ArrayList<>();
        for(char c : pChars) {
            aToZ[c - 'a']++;
        }
        for(int i = 0; i < sChars.length; i++) {
            if(i >= pChars.length) {
                curAtoZ[sChars[i -pChars.length] - 'a']--;
            }
            curAtoZ[sChars[i] - 'a']++;
            if(Arrays.equals(curAtoZ, aToZ)) {
                result.add(i - pChars.length + 1);
            }
        }
        return result;
    }
    public List<Integer> findAnagrams2(String s, String p) {
        List<Integer> ans = new ArrayList<>();
        int sLen = s.length();
        int pLen = p.length();
        for (int i = 0; i < sLen; i++) {
            if (i + pLen > sLen) {
                break;
            }
            String tmp = s.substring(i, i + pLen);
            if (isAnagrams(tmp, p)) {
                ans.add(i);
            }
        }
        return ans;
    }

    private boolean isAnagrams(String tmp, String p) {
        if (tmp == null || p == null || tmp.length() != p.length()) {
            return false;
        }
        int[] dict = new int[26];
        for (int i = 0; i < tmp.length(); i++) {
            dict[tmp.charAt(i) - 'a']++;
        }
        for(int i = 0; i < p.length(); i++) {
            char ch = p.charAt(i);
            dict[ch - 'a']--;
            if(dict[ch - 'a'] < 0) { return false; }
        }
        return true;
    }
}
